COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00006 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a43.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Solution to Hopcroft and Ullman, Exercise 1.4 (Revised).\hfill}

Definition 2)c) must be interpreted to mean $w≠\epsilon$, $x≠\epsilon$,
or the definition is circular. Without the restriction, I~could let
$w=($, $x=\epsilon$, $wx=($, to count~$($ as a balanced string.

Let $S$ be the set of strings meeting def.~1, and $T$ be the set meeting
def.~2. If $w\in S$, we show by course-of-values induction that $w\in T$.

\smallskip
\disleft 20pt:(A):
If $w=\epsilon$, $w\in T$.

\smallskip
\disleft 20pt:(B):
If the cumulative excess of `$($' over `$)$' goes to zero somewhere
inside~$w$, we get $w=xy$, $x\in S$, $y\in S$, both shorter than~$w$.
By (course-of-values) hypothesis, $x\in T$, $y\in T$, so $xy\in T$.

\smallskip
\disleft 20pt:(C):
If $w≠\epsilon$ and the cumulative excess stays $≥1$, then $w=(x)$ for
some~$x$ in~$S$. By induction, $x\in T$, so $w\in T$.

\smallskip
Conversely, suppose $x\in T$.

\smallskip
\disleft 20pt:(A):
If $x=\epsilon$, trivially $x\in S$.

\smallskip
\disleft 20pt:(B):
If $x=(y)$, and $y\in T$, assume by induction $y\in S$. Then the excess
for~$x$ is that for~$y$; that for proper prefixes of $(y)$ is clearly
$≥1$, and so $≥0$.

\smallskip
\disleft 20pt:(C):
If $x=yz$, $y\in T$, $z\in T$, neither empty (why?), assume by induction
$y\in S$, $z\in S$. Then the excess for~$x$ is that for~$y$ plus that 
for~$z$, or~0;  that for prefixes also works out (check).

So $S⊂T$, $T⊂S$, $S=T$.




\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd
First draft (not published)
May 6, 1986.
%revised date;
%subsequently revised.

\bye